구간 트리 [알고리즘] 백준 2042 숫자들의 부분합을 구하는 문제다. 예를 들어 1~10까지 배열에 있으면 2~4까지 합은 9다. 매번 구간을 순회한다면 n^2에 시간복잡도가 나올것이다. 그래서 이 시간 복잡도를 줄이기위해 이진 트리를 이용한다. 노드마다 범위를 정하고 자식들이 부모의 범위를 반씩 저장한다. 예를 들어 1번부터 5번까지 1~5를 저장한다면 다음과 같다. 말단 노드에는 해당 배열 값이 들어가고 부모노드는 자식노드... 구간 트리알고리즘세그먼트 트리구간 트리
[알고리즘] 백준 2042 숫자들의 부분합을 구하는 문제다. 예를 들어 1~10까지 배열에 있으면 2~4까지 합은 9다. 매번 구간을 순회한다면 n^2에 시간복잡도가 나올것이다. 그래서 이 시간 복잡도를 줄이기위해 이진 트리를 이용한다. 노드마다 범위를 정하고 자식들이 부모의 범위를 반씩 저장한다. 예를 들어 1번부터 5번까지 1~5를 저장한다면 다음과 같다. 말단 노드에는 해당 배열 값이 들어가고 부모노드는 자식노드... 구간 트리알고리즘세그먼트 트리구간 트리